package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Objects;

public class Main {

	public static void main(String[] args) {

		Node root = new Node();
		root.left = new Node();
		root.left.left = new Node();
		root.left.right = new Node();
		root.left.right.left = new Node();
		root.right = new Node();
		root.right.right = new Node();
		System.out.println(isBalance0(root));

	}

	/**
	 * 需要在每个节点上做depth操作，效率低下
	 * 
	 * @param node
	 * @return
	 */
	public static boolean isBalance(Node node) {
		if (node == null) {
			return true;
		}
		int lDepth = depth(node.left);
		int rDepth = depth(node.right);
		if (Math.abs(lDepth - rDepth) > 1) {
			return false;
		}
		return isBalance(node.left) && isBalance(node.right);
	}

	public static boolean isBalance0(Node node) {

		return checkHigh(node) < 0 ? false : true;
	}

	private static int checkHigh(Node node) {

		if (node == null) {
			return 0;
		}
		int lHigh = checkHigh(node.left);
		if (lHigh < 0) {
			return -1;
		}
		int rHigh = checkHigh(node.right);
		if (rHigh < 0) {
			return -1;
		}
		if (Math.abs(lHigh - rHigh) > 1) {
			return -1;
		} else {
			return lHigh > rHigh ? lHigh + 1 : rHigh + 1;
		}

	}

	public static int depth(Node node) {

		if (node == null) {
			return 0;
		}
		int lDepth = depth(node.left) + 1;
		int rDepth = depth(node.right) + 1;
		return lDepth > rDepth ? lDepth : rDepth;
	}
}

class Node {

	public Node left;
	public Node right;

	public Node() {

	}
}
